<!DOCTYPE html>
<html lang="zh-CN">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>编译原理知识点汇总 | 月藤的博客</title>
    <meta name="generator" content="VuePress 1.8.0">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/github-markdown-css/2.10.0/github-markdown.min.css">
    <meta name="description" content="简单的介绍">
    
    <link rel="preload" href="/assets/css/0.styles.a2e941e0.css" as="style"><link rel="preload" href="/assets/js/app.c7d9ff18.js" as="script"><link rel="preload" href="/assets/js/2.cd56dec9.js" as="script"><link rel="preload" href="/assets/js/3.a0dd59cc.js" as="script"><link rel="prefetch" href="/assets/js/10.21f484f8.js"><link rel="prefetch" href="/assets/js/11.5e166696.js"><link rel="prefetch" href="/assets/js/12.c56c19a2.js"><link rel="prefetch" href="/assets/js/13.3e31b609.js"><link rel="prefetch" href="/assets/js/14.3db3e5e6.js"><link rel="prefetch" href="/assets/js/15.cc75d7c3.js"><link rel="prefetch" href="/assets/js/16.5546d343.js"><link rel="prefetch" href="/assets/js/17.69b8a0f2.js"><link rel="prefetch" href="/assets/js/18.271396c8.js"><link rel="prefetch" href="/assets/js/19.bd4b0386.js"><link rel="prefetch" href="/assets/js/20.4a48d936.js"><link rel="prefetch" href="/assets/js/21.23862f34.js"><link rel="prefetch" href="/assets/js/22.95b3bd0a.js"><link rel="prefetch" href="/assets/js/23.d7c85d8e.js"><link rel="prefetch" href="/assets/js/24.c6d6dd3c.js"><link rel="prefetch" href="/assets/js/25.bb664de8.js"><link rel="prefetch" href="/assets/js/26.619789c7.js"><link rel="prefetch" href="/assets/js/27.54beb19d.js"><link rel="prefetch" href="/assets/js/28.8d77923a.js"><link rel="prefetch" href="/assets/js/29.7a771891.js"><link rel="prefetch" href="/assets/js/30.73e03cd7.js"><link rel="prefetch" href="/assets/js/31.a9a1ae37.js"><link rel="prefetch" href="/assets/js/32.66082a76.js"><link rel="prefetch" href="/assets/js/33.73a91496.js"><link rel="prefetch" href="/assets/js/34.da867ae2.js"><link rel="prefetch" href="/assets/js/35.6fac5ae2.js"><link rel="prefetch" href="/assets/js/36.0d6f5d22.js"><link rel="prefetch" href="/assets/js/37.c16a4955.js"><link rel="prefetch" href="/assets/js/38.3391e103.js"><link rel="prefetch" href="/assets/js/39.2e00541f.js"><link rel="prefetch" href="/assets/js/4.7f4b5eea.js"><link rel="prefetch" href="/assets/js/40.22b54e67.js"><link rel="prefetch" href="/assets/js/41.ea3ea4f8.js"><link rel="prefetch" href="/assets/js/42.3ae1db24.js"><link rel="prefetch" href="/assets/js/43.ecd8c202.js"><link rel="prefetch" href="/assets/js/44.f7609015.js"><link rel="prefetch" href="/assets/js/45.0db6f0b1.js"><link rel="prefetch" href="/assets/js/46.e28c1031.js"><link rel="prefetch" href="/assets/js/47.32d7164d.js"><link rel="prefetch" href="/assets/js/48.3aeaffda.js"><link rel="prefetch" href="/assets/js/49.33dab1c0.js"><link rel="prefetch" href="/assets/js/5.80c2b38b.js"><link rel="prefetch" href="/assets/js/50.6e41bca8.js"><link rel="prefetch" href="/assets/js/51.37e89a7c.js"><link rel="prefetch" href="/assets/js/52.e60e1d45.js"><link rel="prefetch" href="/assets/js/53.7a9c00ba.js"><link rel="prefetch" href="/assets/js/54.a214a30e.js"><link rel="prefetch" href="/assets/js/6.133fd621.js"><link rel="prefetch" href="/assets/js/7.79403511.js"><link rel="prefetch" href="/assets/js/8.04726c3a.js"><link rel="prefetch" href="/assets/js/9.a86daf82.js">
    <link rel="stylesheet" href="/assets/css/0.styles.a2e941e0.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">月藤的博客</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="https://ziphold.gitee.io/blog/#/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  旧博客（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://rattonlzh.github.io/homepage/homepage.html" target="_blank" rel="noopener noreferrer" class="nav-link external">
  常用网址导航（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="Select language" class="dropdown-title"><span class="title">Languages</span> <span class="arrow down"></span></button> <button type="button" aria-label="Select language" class="mobile-dropdown-title"><span class="title">Languages</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/知识点总结/编译原理知识点汇总.html" class="nav-link">
  zh-CN
</a></li><li class="dropdown-item"><!----> <a href="/en/" class="nav-link">
  en-US
</a></li></ul></div></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><div class="avatar"><img src="/assets/img/avatar.2b77755b.png" alt srcset></div> <div style="z-index: 999"><iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width="298" height="52" src="//music.163.com/outchain/player?type=2&id=28283137&auto=1&height=32"></iframe></div> <nav class="nav-links"><div class="nav-item"><a href="https://ziphold.gitee.io/blog/#/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  旧博客（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://rattonlzh.github.io/homepage/homepage.html" target="_blank" rel="noopener noreferrer" class="nav-link external">
  常用网址导航（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="Select language" class="dropdown-title"><span class="title">Languages</span> <span class="arrow down"></span></button> <button type="button" aria-label="Select language" class="mobile-dropdown-title"><span class="title">Languages</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/知识点总结/编译原理知识点汇总.html" class="nav-link">
  zh-CN
</a></li><li class="dropdown-item"><!----> <a href="/en/" class="nav-link">
  en-US
</a></li></ul></div></div> <!----></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>随便说说</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>知识点总结</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/知识点总结/git总结.html" class="sidebar-link">git总结</a></li><li><a href="/知识点总结/java单元测试总结.html" class="sidebar-link">java测试</a></li><li><a href="/知识点总结/jquery总结.html" class="sidebar-link">jquery初探</a></li><li><a href="/知识点总结/js总结.html" class="sidebar-link">js易错点</a></li><li><a href="/知识点总结/kotlin语法总结.html" class="sidebar-link">kotlin语法入门</a></li><li><a href="/知识点总结/latex总结.html" class="sidebar-link">latex常用代码</a></li><li><a href="/知识点总结/PS总结.html" class="sidebar-link">PS总结</a></li><li><a href="/知识点总结/springboot总结.html" class="sidebar-link">springboot进行web开发总结</a></li><li><a href="/知识点总结/thinkphp总结.html" class="sidebar-link">thinkphp入坑</a></li><li><a href="/知识点总结/uml软件建模总结.html" class="sidebar-link">uml软件建模总结</a></li><li><a href="/知识点总结/人工智能总结.html" class="sidebar-link">人工智能总结</a></li><li><a href="/知识点总结/大数据软件工程总结.html" class="sidebar-link">大数据软件工程总结</a></li><li><a href="/知识点总结/常用快捷键总结.html" class="sidebar-link">第一篇博客</a></li><li><a href="/知识点总结/数字图像处理总结.html" class="sidebar-link">数字图像处理知识点</a></li><li><a href="/知识点总结/数据库应用理论总结.html" class="sidebar-link">数据库应用复习</a></li><li><a href="/知识点总结/数据库系统概念总结.html" class="sidebar-link">数据库系统概念总结</a></li><li><a href="/知识点总结/数据挖掘总结.html" class="sidebar-link">数据挖掘总结</a></li><li><a href="/知识点总结/编译原理知识点汇总.html" class="active sidebar-link">编译原理知识点汇总</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#程序语言的分类" class="sidebar-link">程序语言的分类</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#程序翻译的方式有几种-有何不同" class="sidebar-link">程序翻译的方式有几种？有何不同？</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#编译程序包含有多少个阶段-各阶段的功能任务分别是什么" class="sidebar-link">编译程序包含有多少个阶段，各阶段的功能任务分别是什么？</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#正则表达式-nfa-dfa-dfa最小化" class="sidebar-link">正则表达式$\rightarrow$ NFA $\rightarrow$ DFA $\rightarrow$ DFA最小化</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#词法分析程序的生成方法" class="sidebar-link">词法分析程序的生成方法</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#文法、语言" class="sidebar-link">文法、语言？</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#文法的分类是怎样的-它们之间有何关系" class="sidebar-link">文法的分类是怎样的？它们之间有何关系？</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#推导、规约、语法树、文法的二义性" class="sidebar-link">推导、规约、语法树、文法的二义性？</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#如何画语法树" class="sidebar-link">如何画语法树？</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#文法二义性的消除方法有多少种" class="sidebar-link">文法二义性的消除方法有多少种？</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#自顶向下分析法的问题分析" class="sidebar-link">自顶向下分析法的问题分析</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#递归下降语法分析-方法" class="sidebar-link">递归下降语法分析 方法</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#ll-1-分析方法" class="sidebar-link">LL（1）分析方法</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#first与follow集合" class="sidebar-link">first与follow集合</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#lr-0-dfa-lr-1-dfa-lalr-1-dfa" class="sidebar-link">LR(0)DFA, LR(1)DFA, LALR(1)DFA?</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#lr-0-分析表、lr-1-分析表、slr-1-分析表、lalr-1-分析表" class="sidebar-link">LR(0)分析表、LR(1)分析表、SLR(1)分析表、LALR(1)分析表？</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#lr-0-文法、lr-1-文法、slr-1-文法、lalr-1-文法" class="sidebar-link">LR(0)文法、LR(1)文法、SLR(1)文法、LALR(1)文法？</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#如何利用lr-0-、lr-1-、slr-1-、lalr-1-进行语法分析" class="sidebar-link">如何利用LR(0)、LR(1)、SLR(1)、LALR(1)进行语法分析？</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#语法制导翻译的方法有多少种" class="sidebar-link">语法制导翻译的方法有多少种？</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#中间代码-表示形式如何" class="sidebar-link">中间代码？表示形式如何？</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#如何将一个算术表达式转换为逆波兰表示、四元组表示、三元组表示" class="sidebar-link">如何将一个算术表达式转换为逆波兰表示、四元组表示、三元组表示</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#如何将一段代码翻译为中间代码-后缀、三元组、四元组" class="sidebar-link">如何将一段代码翻译为中间代码（后缀、三元组、四元组）</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#几种常用语句的翻译-能写出语义函数或语义动作" class="sidebar-link">几种常用语句的翻译——能写出语义函数或语义动作</a></li><li class="sidebar-sub-header"><a href="/知识点总结/编译原理知识点汇总.html#课堂笔记" class="sidebar-link">课堂笔记</a></li></ul></li><li><a href="/知识点总结/设计模式总结.html" class="sidebar-link">设计模式</a></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>考研专区</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>读书笔记</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>开发资料</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>配置记录</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>思维导图</span> <span class="arrow right"></span></p> <!----></section></li><li><a href="/friend_link.html" class="sidebar-link">友情链接</a></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="编译原理知识点汇总"><a href="#编译原理知识点汇总" class="header-anchor">#</a> 编译原理知识点汇总</h1> <h2 id="程序语言的分类"><a href="#程序语言的分类" class="header-anchor">#</a> 程序语言的分类</h2> <p>机器语言、汇编语言、高级程序语言</p> <h2 id="程序翻译的方式有几种-有何不同"><a href="#程序翻译的方式有几种-有何不同" class="header-anchor">#</a> 程序翻译的方式有几种？有何不同？</h2> <p>2种；分别是编译和解释。编译翻译是将整个源程序翻译为目标代码后才能执行；解释翻译是立即执行源程序，将源程序一条一条地解释成机器语言随即交由计算机执行，翻译与执行是同步的。</p> <h2 id="编译程序包含有多少个阶段-各阶段的功能任务分别是什么"><a href="#编译程序包含有多少个阶段-各阶段的功能任务分别是什么" class="header-anchor">#</a> 编译程序包含有多少个阶段，各阶段的功能任务分别是什么？</h2> <p>6个阶段；</p> <p>扫描程序阶段：执行词法分析，从字符流中收集字符序列到称作记号的有意义单元中</p> <p>语法分析阶段：从扫描程序中获取记号形式的源码，完成定义程序结构元素及关系的工作。</p> <p>语义分析阶段：分析静态语义（包括声明和类型检查），得到程序计算的额外信息</p> <p>源代码优化阶段：完成代码优化</p> <p>代码生成阶段：生成目标代码</p> <p>目标代码优化阶段：改进目标代码，将速度慢的指令改成速度快的，删除冗余操作</p> <h2 id="正则表达式-nfa-dfa-dfa最小化"><a href="#正则表达式-nfa-dfa-dfa最小化" class="header-anchor">#</a> 正则表达式<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>→</mo></mrow><annotation encoding="application/x-tex">\rightarrow</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.36687em;"></span><span class="strut bottom" style="height:0.36687em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mrel">→</span></span></span></span> NFA <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>→</mo></mrow><annotation encoding="application/x-tex">\rightarrow</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.36687em;"></span><span class="strut bottom" style="height:0.36687em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mrel">→</span></span></span></span> DFA <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>→</mo></mrow><annotation encoding="application/x-tex">\rightarrow</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.36687em;"></span><span class="strut bottom" style="height:0.36687em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mrel">→</span></span></span></span> DFA最小化</h2> <h3 id="正则表达式转nfa"><a href="#正则表达式转nfa" class="header-anchor">#</a> 正则表达式转nfa：</h3> <p>Thomson方法</p> <p><img src="/assets/img/1578479923192.f8e5b0ea.png" alt="1578479923192"></p> <p><img src="/assets/img/1578479942312.529ec99a.png" alt="1578479942312"></p> <p><img src="/assets/img/1578479970329.97a86031.png" alt="1578479970329"></p> <p><img src="/assets/img/1578479995694.57745a83.png" alt="1578479995694"></p> <h3 id="nfa转dfa"><a href="#nfa转dfa" class="header-anchor">#</a> nfa转dfa：</h3> <p><img src="/assets/img/1578480133670.503012a1.png" alt="1578480133670"></p> <p><img src="/assets/img/1578480151254.8ec5a77d.png" alt="1578480151254"></p> <p><img src="/assets/img/1578469611297.d4a2e692.png" alt="1578469611297"></p> <h3 id="dfa转dfa最小化"><a href="#dfa转dfa最小化" class="header-anchor">#</a> dfa转dfa最小化：</h3> <p>创建两个集合，其中之一包含了所有的接受状态，而另一个则由所有的非接受状态组成。</p> <p>如果接受状态s 和t 在a上有转换且位于不同的集合，则这组状态不能定义任何a- 转换，此时就称作a 区分（d i s t i n g u i s h）了状态s 和t，按a划分成两个集合。</p> <p>重复以上操作一直持续到所有集合只有一个元素（在这种情况下，就显示原始D FA为最小）或一直是到再没有集合可以分隔了。</p> <p><img src="/assets/img/1578485128848.50e48d56.png" alt="1578485128848"></p> <p><img src="/assets/img/1578485151074.fb09c685.png" alt="1578485151074"></p> <h3 id="正则表达式转dfa"><a href="#正则表达式转dfa" class="header-anchor">#</a> 正则表达式转dfa：</h3> <p><img src="/assets/img/1578481241785.fe0c67a7.png" alt="1578481241785"></p> <p><img src="/assets/img/1578482173486.830092c5.png" alt="1578482173486"></p> <p><img src="/assets/img/1578482790540.0e89020e.png" alt="1578482790540"></p> <h2 id="词法分析程序的生成方法"><a href="#词法分析程序的生成方法" class="header-anchor">#</a> 词法分析程序的生成方法</h2> <ol><li>状态转换方法</li></ol> <p><img src="/assets/img/1578481830090.86fa6f4a.png" alt="1578481830090"></p> <p><img src="/assets/img/1578481906538.1820cc11.png" alt="1578481906538"></p> <p><img src="/assets/img/1578481939723.8f3cca31.png" alt="1578481939723"></p> <ol start="2"><li><p>转换表</p> <p><img src="/assets/img/1578481990515.fcc0d522.png" alt="1578481990515"></p></li> <li><p>使用lex生成词法分析的代码</p></li></ol> <h2 id="文法、语言"><a href="#文法、语言" class="header-anchor">#</a> 文法、语言？</h2> <p>文法：用于描述语言的语法结构，用四元组表示 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>&lt;</mo><mi>V</mi><mi>N</mi><mo separator="true">,</mo><mi>V</mi><mi>T</mi><mo separator="true">,</mo><mi>P</mi><mo separator="true">,</mo><mi>S</mi><mo>&gt;</mo></mrow><annotation encoding="application/x-tex">&lt;VN,VT,P,S&gt;</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.8777699999999999em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mrel">&lt;</span><span class="mord mathit" style="margin-right:0.22222em;">V</span><span class="mord mathit" style="margin-right:0.10903em;">N</span><span class="mpunct">,</span><span class="mord mathit" style="margin-right:0.22222em;">V</span><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="mpunct">,</span><span class="mord mathit" style="margin-right:0.13889em;">P</span><span class="mpunct">,</span><span class="mord mathit" style="margin-right:0.05764em;">S</span><span class="mrel">&gt;</span></span></span></span>，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>V</mi><mi>N</mi></mrow><annotation encoding="application/x-tex">VN</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.22222em;">V</span><span class="mord mathit" style="margin-right:0.10903em;">N</span></span></span></span>表示非终结符集，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>V</mi><mi>T</mi></mrow><annotation encoding="application/x-tex">VT</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.22222em;">V</span><span class="mord mathit" style="margin-right:0.13889em;">T</span></span></span></span>表示终结符集，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>S</mi></mrow><annotation encoding="application/x-tex">S</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.05764em;">S</span></span></span></span>是开始符号集，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>P</mi></mrow><annotation encoding="application/x-tex">P</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.13889em;">P</span></span></span></span>是产生式集</p> <p><img src="/assets/img/1578537070447.1d6444cb.png" alt="1578537070447"></p> <p><img src="/assets/img/1578535929990.3b541bdd.png" alt="1578535929990"></p> <h2 id="文法的分类是怎样的-它们之间有何关系"><a href="#文法的分类是怎样的-它们之间有何关系" class="header-anchor">#</a> 文法的分类是怎样的？它们之间有何关系？</h2> <p>chomsky分类：</p> <p>0型文法：无限制文法或短语文法</p> <p>1型文法：上下文有关文法.对每个规则 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>α</mi><mo>→</mo><mi>β</mi></mrow><annotation encoding="application/x-tex">\alpha\rightarrow\beta</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.0037em;">α</span><span class="mrel">→</span><span class="mord mathit" style="margin-right:0.05278em;">β</span></span></span></span>都有 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi mathvariant="normal">∣</mi><mi>α</mi><mi mathvariant="normal">∣</mi><mo>≤</mo><mi mathvariant="normal">∣</mi><mi>β</mi><mi mathvariant="normal">∣</mi></mrow><annotation encoding="application/x-tex">|\alpha|\le|\beta|</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">∣</span><span class="mord mathit" style="margin-right:0.0037em;">α</span><span class="mord mathrm">∣</span><span class="mrel">≤</span><span class="mord mathrm">∣</span><span class="mord mathit" style="margin-right:0.05278em;">β</span><span class="mord mathrm">∣</span></span></span></span>,即产生式左部的长度不超右部的长度。上下文有关是指对非终结符进行替换时，要考虑上下文的环境。</p> <p>2型文法：对 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>α</mi><mo>→</mo><mi>β</mi></mrow><annotation encoding="application/x-tex">\alpha\rightarrow\beta</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.8888799999999999em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.0037em;">α</span><span class="mrel">→</span><span class="mord mathit" style="margin-right:0.05278em;">β</span></span></span></span>的 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>α</mi></mrow><annotation encoding="application/x-tex">\alpha</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.43056em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.0037em;">α</span></span></span></span>是单个终结符，也叫上下文无关文法</p> <p>3型文法：也叫正规文法，每个规则特点为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>A</mi><mo>→</mo><mi>a</mi><mi>B</mi></mrow><annotation encoding="application/x-tex">A\rightarrow aB</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">A</span><span class="mrel">→</span><span class="mord mathit">a</span><span class="mord mathit" style="margin-right:0.05017em;">B</span></span></span></span>或 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>A</mi><mo>→</mo><mi>a</mi></mrow><annotation encoding="application/x-tex">A\rightarrow a</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">A</span><span class="mrel">→</span><span class="mord mathit">a</span></span></span></span>,也叫右线性文法。也可以定义成左线性的，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>A</mi><mo>→</mo><mi>B</mi><mi>a</mi></mrow><annotation encoding="application/x-tex">A\rightarrow Ba</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">A</span><span class="mrel">→</span><span class="mord mathit" style="margin-right:0.05017em;">B</span><span class="mord mathit">a</span></span></span></span>或 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>A</mi><mo>→</mo><mi>a</mi></mrow><annotation encoding="application/x-tex">A\rightarrow a</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathit">A</span><span class="mrel">→</span><span class="mord mathit">a</span></span></span></span>（左线性文法）</p> <p>i型文法的能力比i+1型文法的能力强</p> <h2 id="推导、规约、语法树、文法的二义性"><a href="#推导、规约、语法树、文法的二义性" class="header-anchor">#</a> 推导、规约、语法树、文法的二义性？</h2> <p>推导：自顶向下分析（top-down parsing)</p> <p>规约：自底向上分析（bottom-up parsing)</p> <p>分析树：</p> <p><img src="/assets/img/1578537717730.51710bd1.png" alt="1578537717730"></p> <p>语法树</p> <p><img src="/assets/img/1578537913797.a2bb5bbb.png" alt="996123"></p> <h2 id="如何画语法树"><a href="#如何画语法树" class="header-anchor">#</a> 如何画语法树？</h2> <p><img src="/assets/img/1578538446930.4f345db9.png" alt="1578538446930"></p> <p><img src="/assets/img/1578538460763.c1541f93.png" alt="1578538460763"></p> <h2 id="文法二义性的消除方法有多少种"><a href="#文法二义性的消除方法有多少种" class="header-anchor">#</a> 文法二义性的消除方法有多少种？</h2> <p>两种，制定消除二义性的限制规则，另一种是文法改造，解决彻底，新文法适合语法分析的自动生成，缺点是改错复杂</p> <h3 id="运算优先级二义性的消除"><a href="#运算优先级二义性的消除" class="header-anchor">#</a> 运算优先级二义性的消除</h3> <p><img src="/assets/img/1578538992533.3d1deb50.png" alt="1578538992533"></p> <p><img src="/assets/img/1578538970115.64517f36.png" alt="1578538970115"></p> <p><img src="/assets/img/1578539529098.c6e98f3d.png" alt="1578539529098"></p> <h3 id="悬挂else问题的解决"><a href="#悬挂else问题的解决" class="header-anchor">#</a> 悬挂else问题的解决</h3> <ol><li>制定限制规则，在语法分析程序实现，else一定要与最近的if匹配</li> <li>改造文法</li> <li>重新设计语法，如else一定要出现或用与if语句匹配的关键字（如endif）标识语句的结束</li></ol> <p><img src="/assets/img/1578539857003.9d52764d.png" alt="1578539857003"></p> <p><img src="/assets/img/1578539898161.4688b5fc.png" alt="1578539898161"></p> <h3 id="左递归的消除"><a href="#左递归的消除" class="header-anchor">#</a> 左递归的消除</h3> <p>EBNF：扩充BNF，在规则中可表示重复和可选</p> <p><img src="/assets/img/1578540460613.6fe7a0d5.png" alt="1578540460613"></p> <p><img src="/assets/img/1578540520028.ead19211.png" alt="1578540520028"></p> <p><img src="/assets/img/1578540569888.d65d6498.png" alt="1578540569888"></p> <p><img src="/assets/img/1578540632311.7c1651e7.png" alt="1578540632311"></p> <p><img src="/assets/img/1578540644078.86d727a3.png" alt="1578540644078"></p> <h2 id="自顶向下分析法的问题分析"><a href="#自顶向下分析法的问题分析" class="header-anchor">#</a> 自顶向下分析法的问题分析</h2> <p>递归下降子程序表示文法识别串的过程</p> <p>提取公因子</p> <p>消除左递归：对所有非终结符遍历，如果包含已消除左递归的非终结符的则代入替换该终结符再进行左递归的判断；判断出现左递归的，消除左递归，</p> <h2 id="递归下降语法分析-方法"><a href="#递归下降语法分析-方法" class="header-anchor">#</a> 递归下降语法分析 方法</h2> <p>判断是否存在左递归和公因子，如果有就改写文法。</p> <p>改写成EBNF扩充文法，用while循环和if分支分别表示重复和可选</p> <p>用函数定义表示上下文无关文法，函数调用表示匹配非终结符，用match()函数匹配终结符</p> <p>问题：分析效率低，所以有了ll（1）分析法</p> <h2 id="ll-1-分析方法"><a href="#ll-1-分析方法" class="header-anchor">#</a> LL（1）分析方法</h2> <h2 id="first与follow集合"><a href="#first与follow集合" class="header-anchor">#</a> first与follow集合</h2> <p>first集：每一条规则的非终结符开头的所有头一个终结符</p> <p><img src="/assets/img/1578546635611.ef5a1008.png" alt="1578546635611"></p> <p><img src="/assets/img/1578546969301.aaedd680.png" alt="1578546969301"></p> <p><img src="/assets/img/1578547104466.f87da84b.png" alt="1578547104466"></p> <p><img src="/assets/img/1578549031260.5b19612b.png" alt="1578549031260"></p> <h2 id="lr-0-dfa-lr-1-dfa-lalr-1-dfa"><a href="#lr-0-dfa-lr-1-dfa-lalr-1-dfa" class="header-anchor">#</a> LR(0)DFA, LR(1)DFA, LALR(1)DFA?</h2> <h2 id="lr-0-分析表、lr-1-分析表、slr-1-分析表、lalr-1-分析表"><a href="#lr-0-分析表、lr-1-分析表、slr-1-分析表、lalr-1-分析表" class="header-anchor">#</a> LR(0)分析表、LR(1)分析表、SLR(1)分析表、LALR(1)分析表？</h2> <h2 id="lr-0-文法、lr-1-文法、slr-1-文法、lalr-1-文法"><a href="#lr-0-文法、lr-1-文法、slr-1-文法、lalr-1-文法" class="header-anchor">#</a> LR(0)文法、LR(1)文法、SLR(1)文法、LALR(1)文法？</h2> <h2 id="如何利用lr-0-、lr-1-、slr-1-、lalr-1-进行语法分析"><a href="#如何利用lr-0-、lr-1-、slr-1-、lalr-1-进行语法分析" class="header-anchor">#</a> 如何利用LR(0)、LR(1)、SLR(1)、LALR(1)进行语法分析？</h2> <h2 id="语法制导翻译的方法有多少种"><a href="#语法制导翻译的方法有多少种" class="header-anchor">#</a> 语法制导翻译的方法有多少种？</h2> <p>四种，</p> <h2 id="中间代码-表示形式如何"><a href="#中间代码-表示形式如何" class="header-anchor">#</a> 中间代码？表示形式如何？</h2> <h2 id="如何将一个算术表达式转换为逆波兰表示、四元组表示、三元组表示"><a href="#如何将一个算术表达式转换为逆波兰表示、四元组表示、三元组表示" class="header-anchor">#</a> 如何将一个算术表达式转换为逆波兰表示、四元组表示、三元组表示</h2> <h2 id="如何将一段代码翻译为中间代码-后缀、三元组、四元组"><a href="#如何将一段代码翻译为中间代码-后缀、三元组、四元组" class="header-anchor">#</a> 如何将一段代码翻译为中间代码（后缀、三元组、四元组）</h2> <h2 id="几种常用语句的翻译-能写出语义函数或语义动作"><a href="#几种常用语句的翻译-能写出语义函数或语义动作" class="header-anchor">#</a> 几种常用语句的翻译——能写出语义函数或语义动作</h2> <ol><li>算术表达式</li> <li>说明语句</li> <li>赋值语句</li> <li>逻辑表达式</li> <li>条件判断语句——if语句</li> <li>循环语句——while、repeat、for语句</li> <li>扩展到其他程序设计语句</li></ol> <h1 id="warning"><a href="#warning" class="header-anchor">#</a> warning</h1> <p>dfa中带中括号的输入符号表示在识别过程中不消耗该字符</p> <p><img src="/assets/img/1578724997887.d54f4a4a.png" alt="1578724997887"></p> <p>词法分析中将多个dfa合并的方法：初始状态合并成一个，原dfa的接受状态变成非接受状态，增加一个到新接受状态（DONE）的转换，输入符号是[other]，转换成done时，原状态会传递一个记号给done，到达done后将记号返回。</p> <p>dfa扫描中将保留字和标识符看做等同，只需到达done后判断识别出来的符号是否在保留字表格中即可确定接受的是保留字还是标识符。</p> <h3 id="《编译原理与实践》中定义的函数与成员"><a href="#《编译原理与实践》中定义的函数与成员" class="header-anchor">#</a> 《编译原理与实践》中定义的函数与成员</h3> <p><code>lineBuf[]</code>：缓存从源代码读取的当前行</p> <p><code>tokenString[]</code>:标识符或保留字的串值</p> <p><code>reservedWords[]</code>:保留字数组，数据类型是结构体，包含字符串类型的串值和枚举类型的记号</p> <p><code>reservedLookUp(char*)</code>：查找识别的字符串是否在保留字数组中，如果在则返回对应的保留字记号，否则返回标识符记号</p> <p><code>getToken()</code>:消耗字符并返回一个识别的记号</p> <p><code>getNextChar()</code>:获取一行中的下一个字符，如果已经到达行尾，则读取新行的第一个字符</p> <p><code>ungetNextChar()</code>:如果没有到达文件尾部，则将指针指向上一个位置</p> <p><code>isdigit()</code>:输入一个字符的ascii值，如果属于数字范围则返回true;否则返回false</p> <p><code>isalpha()</code>:输入一个字符的ascii值，如果属于字母返回则返回true；否则返回false</p> <p><code>match()</code>:匹配token，如果匹配则识别下一个字符，否则出错</p> <h2 id="课堂笔记"><a href="#课堂笔记" class="header-anchor">#</a> 课堂笔记</h2> <h3 id="消除二义性"><a href="#消除二义性" class="header-anchor">#</a> 消除二义性</h3> <p>可以通过重写文法消除二义性。重写方法有两种结果，一种需要同时改变正在识别的基本串，一种不需要改变正在识别的语言。前者的应用价值甚微，下面我们只考虑不会改变语言的方式重写文法。</p> <h3 id="处理运算优先权和消除"><a href="#处理运算优先权和消除" class="header-anchor">#</a> 处理运算优先权和消除</h3> <p>构造级联分析树：相同的优选权的算符归到同一组,更高优先级的算符的离语法树的根更远，将规则重写为左递归规则或右递归规则（对于文法右边的出现两次相同非终结符的表达式，用新的非终结符代替其中一个）</p> <p>未消除二义性的文法</p>
\begin{align*}
exp &amp;\rightarrow exp\ addop\ exp\ |\ term\\
addop &amp;\rightarrow +|-\\
term &amp;\rightarrow exp\ mulop\ exp\ |\ number\\
mulop &amp; \rightarrow \times|\div
\end{align*}

<p>消除二义性后的文法</p>
\begin{align*}
exp &amp; \rightarrow exp \ addop \ term \ | \ term \\
addop &amp; \rightarrow + | - \\
term &amp; \rightarrow term \ mulop \ exp \ | \ number\\
mulop &amp; \rightarrow \times | \div
\end{align*}

<h3 id="悬挂else的消除"><a href="#悬挂else的消除" class="header-anchor">#</a> 悬挂else的消除</h3> <p>文法右边的表达式同时是该文法的另一条表达式的前缀。</p>
\begin{align*}
statement &amp;\rightarrow \text{if-stmt} \ | \ other \\
\text{if-stmt} &amp;\rightarrow if(exp) \ statement \\
&amp; | \ if(exp) \ statement \ else \ statement \\
exp &amp; \rightarrow 0 \ | \ 1 
\end{align*}

<p>最近嵌套规则消除悬挂else,要求出现else之前的语句必须是已匹配的</p>
\begin{align*}
statement &amp; \rightarrow \ \text{matched-stmt} \ | \ \text{unmatched-stmt} \\
\text{matched-stmt} &amp; \rightarrow \ if(exp) \ \text{matched-stmt} \ else \ \text{matched-stmt}\ |\ other\\
\text{unmatched-stmt} &amp; \rightarrow \ if(exp) \ statement \\
&amp; | if(exp) \text{matched-stmt} \ else \ \text{unmatched-stmt}\\
exp &amp; \rightarrow 0|1
\end{align*}

<h3 id="无关紧要的二义性"><a href="#无关紧要的二义性" class="header-anchor">#</a> 无关紧要的二义性</h3> <p>某些文法总是存在二义性且总生成唯一的抽象语法树。由于相结合的语义不必依赖于使用的是哪种消除二义性的规则， 所以可将这样的二义性称作无关紧要的二义性（ inessential ambiguity）。</p></div> <footer class="page-edit"><!----> <!----> <a rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh"><img alt="知识共享许可协议" src="" style="border-width:0"></a><br>本作品采用<a rel="license" href="http://creativecommons.org/licenses/by/4.0/">知识共享署名 4.0 国际许可协议</a>进行许可。

   
</footer> <div class="page-nav"><p class="inner"><span class="prev">
      ←
      <a href="/知识点总结/数据挖掘总结.html" class="prev">
        数据挖掘总结
      </a></span> <span class="next"><a href="/知识点总结/设计模式总结.html">
        设计模式
      </a>
      →
    </span></p></div>  <footer style="text-align:center;">备案号： 粤ICP备2021020303号</footer></main></div><div class="global-ui"><!----></div></div>
    <script src="/assets/js/app.c7d9ff18.js" defer></script><script src="/assets/js/2.cd56dec9.js" defer></script><script src="/assets/js/3.a0dd59cc.js" defer></script>
  </body>
</html>
